<html>
<head><meta charset="utf-8"><title>add nsw + sadd.with.overflow · t-compiler/wg-llvm · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/index.html">t-compiler/wg-llvm</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html">add nsw + sadd.with.overflow</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="159761206"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159761206" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159761206">(Mar 02 2019 at 00:02)</a>:</h4>
<p><span class="user-mention" data-user-id="125270">@scottmcm</span> mentioned <a href="https://bugs.llvm.org/show_bug.cgi?id=38146" target="_blank" title="https://bugs.llvm.org/show_bug.cgi?id=38146">https://bugs.llvm.org/show_bug.cgi?id=38146</a> to me a while ago as an upstream LLVM bug that could improve <code>Range::step_by</code> performance</p>



<a name="159761350"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159761350" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159761350">(Mar 02 2019 at 00:04)</a>:</h4>
<p>So would it fall within the goals of this working group?</p>



<a name="159767964"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159767964" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159767964">(Mar 02 2019 at 01:14)</a>:</h4>
<p>yes.</p>



<a name="159794862"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159794862" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159794862">(Mar 02 2019 at 13:02)</a>:</h4>
<p>I believe that one is already resolved by the switch to the usub.add intrinsics, as far as <code>Range::step_by</code> is concerned.</p>



<a name="159795172"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159795172" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159795172">(Mar 02 2019 at 13:11)</a>:</h4>
<p>Though looking at the code it's not clear to me where it would be relevant. In any case, it would be good to have that fold.</p>



<a name="159795311"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159795311" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159795311">(Mar 02 2019 at 13:14)</a>:</h4>
<p>If you're interested in doing this, the place to implement it would be around <a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/InstCombine/InstCombineCalls.cpp#L2019" target="_blank" title="https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/InstCombine/InstCombineCalls.cpp#L2019">https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/InstCombine/InstCombineCalls.cpp#L2019</a>.</p>



<a name="159807665"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159807665" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159807665">(Mar 02 2019 at 17:49)</a>:</h4>
<p><del>This may have actually already been fixed.</del><br>
EDIT: nvm it was a poorly written test</p>



<a name="159811249"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159811249" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159811249">(Mar 02 2019 at 19:28)</a>:</h4>
<p>I've got the following to pass <code>llvm-lit</code>, but I've got some serious cleanup to do.</p>
<div class="codehilite"><pre><span></span>; RUN: opt &lt; %s -instcombine -S | FileCheck %s

declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32)

define { i32, i1 } @fold_uadd_with_overflow(i32) {
  ; CHECK-Label: @fold_add_with_overflow
  ; CHECK:       %2 = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %0, i32 20)
  ; CHECK-NEXT:  ret { i32, i1 } %2
  %2 = add nuw i32 %0, 7
  %3 = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %2, i32 13)
  ret { i32, i1 } %3
}
</pre></div>



<a name="159811277"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159811277" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159811277">(Mar 02 2019 at 19:29)</a>:</h4>
<p>In theory I think we could tackle <code>(s|u)mul</code> and <code>(s|u)sub</code>, but I'm super new to LLVM, so I'd like to keep the scope as small as possible</p>



<a name="159811331"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159811331" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159811331">(Mar 02 2019 at 19:30)</a>:</h4>
<p>So I'll just stick to <code>(s|u)add</code></p>



<a name="159811434"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159811434" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159811434">(Mar 02 2019 at 19:33)</a>:</h4>
<blockquote>
<p>I'd like to keep the scope as small as possible</p>
</blockquote>
<p>thats what LLVM people prefer either way</p>



<a name="159826172"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159826172" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159826172">(Mar 03 2019 at 02:24)</a>:</h4>
<p><a href="https://reviews.llvm.org/D58881" target="_blank" title="https://reviews.llvm.org/D58881">https://reviews.llvm.org/D58881</a></p>



<a name="159826181"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159826181" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159826181">(Mar 03 2019 at 02:25)</a>:</h4>
<p>Decided to just stick to <code>sadd.with.overflow</code>. I'll submit a follow-up for <code>uadd.with.overflow</code></p>



<a name="159887591"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159887591" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159887591">(Mar 04 2019 at 05:08)</a>:</h4>
<p>I think there's a whole series of potential work related to the overflow intrinsics.  For example, it seems like LLVM doesn't know that a non-overflowing multiplication is a multiple of its operands: <a href="https://rust.godbolt.org/z/dNB2xK" target="_blank" title="https://rust.godbolt.org/z/dNB2xK">https://rust.godbolt.org/z/dNB2xK</a></p>



<a name="159897700"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159897700" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159897700">(Mar 04 2019 at 09:19)</a>:</h4>
<p><span class="user-mention" data-user-id="125270">@scottmcm</span> These kind of optimizations are pretty hard to do, because they only apply in code conditioned on the overflow check. That's not a check that can be performed in InstCombine. There's really no good place where such an optimization can go right now.</p>



<a name="159897815"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/159897815" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#159897815">(Mar 04 2019 at 09:21)</a>:</h4>
<p>I think InstCombine does these kinds of optimizations (not for overflow but for comparisons) in some really primitive fashion, like only if the condition is directly on the only predecessor block. Anything else would be too expensive.</p>



<a name="160079885"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160079885" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160079885">(Mar 06 2019 at 09:25)</a>:</h4>
<p><span class="user-mention" data-user-id="133224">@Nikita Popov</span> Ah, so basically anything behind control flow (as opposed to direct SSA use/defs) is impractical, basically?  Makes sense; thanks.</p>



<a name="160435574"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160435574" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160435574">(Mar 10 2019 at 22:27)</a>:</h4>
<p>Status update on sadd.with.overflow: <a href="https://reviews.llvm.org/D58881" target="_blank" title="https://reviews.llvm.org/D58881">https://reviews.llvm.org/D58881</a> has landed and <span class="user-mention" data-user-id="143663">@dlrobertson</span> has submitted a followup in <a href="https://reviews.llvm.org/D59071" target="_blank" title="https://reviews.llvm.org/D59071">https://reviews.llvm.org/D59071</a>. I'm trying to lay some groundwork to turn this into a more general overflow check optimization.</p>



<a name="160442592"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160442592" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160442592">(Mar 11 2019 at 01:10)</a>:</h4>
<p><span class="user-mention" data-user-id="133224">@Nikita Popov</span> awesome work!</p>



<a name="160443420"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160443420" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160443420">(Mar 11 2019 at 01:24)</a>:</h4>
<p>Still trying to wrap my head around it a bit, but I think I see where you're going with it.</p>



<a name="160443654"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160443654" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160443654">(Mar 11 2019 at 01:27)</a>:</h4>
<p>Are there good docs on how the internals of LLVM work? E.g. the rustc guide or even just a few good descriptions of ValueTracking, instcombine, instsimplify, etc?</p>



<a name="160949943"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160949943" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160949943">(Mar 16 2019 at 12:34)</a>:</h4>
<p>As so often, I don't think there's any good docs apart from the language reference and (somewhat less useful) the programmer manual.</p>



<a name="160950071"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160950071" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160950071">(Mar 16 2019 at 12:38)</a>:</h4>
<p>Mostly a matter of looking at what the code around you is doing and trying to copy it :) As to the ones you mentioned, the important distinction is that ConstantFolding deals with folding instructions that have only constant or undef operands, InstSimplify deals with simplifications that don't create new instructions and are relatively cheap (no recursive analysis) and InstCombine does anything else, with the restriction that it should never increase instruction count, to avoid looping. ValueTracking are helper utilities to determine various properties of instructions (known bits, known sign bits, etc), often in a recursive fashion.</p>



<a name="160950144"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160950144" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160950144">(Mar 16 2019 at 12:41)</a>:</h4>
<p>ValueTracking is a bit of a wart (imho) because the proper way to do this would be to sparsely propagate the information with a fixed point algorithm, but the recursive computations are much easier to throw into random places in the compiler. The end effect is that this information is computed again and again and a sizable chunk of compile time may be spent just in known bits calculations.</p>



<a name="160950339"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160950339" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160950339">(Mar 16 2019 at 12:47)</a>:</h4>
<p><span class="user-mention" data-user-id="143663">@dlrobertson</span> In any case, I ended up hijacking the saddo mixed signed patch for the general overflow optimization... In the meantime, would you like to extend the add nsw + saddo changes to the other cases? The add nuw + uaddo case should be fairly simple and integrate well into your existing code.</p>



<a name="160950399"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160950399" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160950399">(Mar 16 2019 at 12:49)</a>:</h4>
<p>The sub case is tricky, because LLVM canonicalizes "sub %x, C" to "add %x, -C" and looses the nuw flag while doing so. For the ssubo case, I think a good way to handle it is to also canonicalize ssubo(X, C) to saddo(X, -C), which means that the existing saddo code will already handle it. (It also has the additional advantage that things like CSE and GVN will know that ssubo(X, C) and saddo(X, -C) are the same.)</p>



<a name="160950481"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160950481" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160950481">(Mar 16 2019 at 12:51)</a>:</h4>
<p>I don't think there's anything that can be done in the usubo case, the necessary nuw information is lost during canonicalization, so no way to get that back...</p>



<a name="160951987"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/160951987" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#160951987">(Mar 16 2019 at 13:35)</a>:</h4>
<p><span class="user-mention" data-user-id="133224">@Nikita Popov</span> Thanks for the info! I read through the lang ref a few years ago, but it might be worthwhile to skim through it again.</p>
<blockquote>
<p>I ended up hijacking the saddo mixed signed patch for the general overflow optimization</p>
</blockquote>
<p>Np. I'll move on to uaddo.</p>
<blockquote>
<p>I think a good way to handle it is to also canonicalize ssubo(X, C) to saddo(X, -C)</p>
</blockquote>
<p>Interesting. I'll try it out</p>



<a name="161244751"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/161244751" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#161244751">(Mar 20 2019 at 13:06)</a>:</h4>
<blockquote>
<p>The sub case is tricky, because LLVM canonicalizes "sub %x, C" to "add %x, -C" and looses the nuw flag while doing so. For the ssubo case,</p>
</blockquote>
<p>Ah! This makes sense now. I was wondering why <code>saddo (X -nsw C0), C1 -&gt; saddo X, C0 - C1</code> "just works"</p>



<a name="161244927"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/161244927" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#161244927">(Mar 20 2019 at 13:08)</a>:</h4>
<p>Is it worth writing a test case for folding <code>sub nsw</code> + <code>saddo</code>? Or is this sufficiently covered by the tests for <code>sub %x, C -&gt; add %x, -C</code> and the current <code>saddo</code> tests?</p>



<a name="161255094"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/161255094" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#161255094">(Mar 20 2019 at 14:59)</a>:</h4>
<p><span class="user-mention" data-user-id="143663">@dlrobertson</span> Well, adding it certainly won't hurt ;) Might also test something fancy like sub nsw %x, SignedMin, which will likely not work (at a guess this is canonicalized to add %x, SignedMin without the nsw flag).</p>



<a name="161255482"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/161255482" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#161255482">(Mar 20 2019 at 15:02)</a>:</h4>
<p><span aria-label="+1" class="emoji emoji-1f44d" role="img" title="+1">:+1:</span> I'll bundle it in with the NFC commit with the baseline tests for <code>ssubo X, C -&gt; saddo X, -C</code></p>



<a name="162909301"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/162909301" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#162909301">(Apr 09 2019 at 13:22)</a>:</h4>
<p><span class="user-mention" data-user-id="133224">@Nikita Popov</span> sorry for being absent recently... I just started a new job... Should be around a bit more again. I'm updating the ssubo diff now</p>



<a name="163020913"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163020913" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163020913">(Apr 10 2019 at 16:33)</a>:</h4>
<p>Okay, the ssubo canonicalization has landed, the ConstantRange based overflow checks have landed and I've just added some missing AlwaysOverflows support. With that, I think we have all the missing InstCombine bits for with.overflow intrinsics.</p>



<a name="163021032"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163021032" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163021032">(Apr 10 2019 at 16:35)</a>:</h4>
<p>I think Rust should consider moving away from uadd.with.overflow and usub.with.overflow though. These have simple IR replacements, which I suspect to optimize better than the intrinsics.</p>



<a name="163021189"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163021189" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163021189">(Apr 10 2019 at 16:37)</a>:</h4>
<p>LLVM can form these intrinsics during CodeGenPrepare if profitable, but I think there's relatively little benefit to using them in IR and a lot of drawbacks.</p>



<a name="163038086"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163038086" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163038086">(Apr 10 2019 at 19:35)</a>:</h4>
<p>what are the "simple IR replacements"?</p>



<a name="163038104"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163038104" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163038104">(Apr 10 2019 at 19:35)</a>:</h4>
<p>doing stuff on a larger <code>iX</code>?</p>



<a name="163050324"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163050324" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163050324">(Apr 10 2019 at 22:01)</a>:</h4>
<p><span class="user-mention" data-user-id="123586">@nagisa</span> The canonical patterns are <code>%add = add iN %x, %y; %ov = icmp ult iN %add, %x</code> and <code>%sub = sub iN %x, %y; %ov = icmp ult %x, %y</code>.</p>



<a name="163091157"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163091157" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163091157">(Apr 11 2019 at 11:30)</a>:</h4>
<p>seems fine to me?</p>



<a name="163091168"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163091168" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163091168">(Apr 11 2019 at 11:31)</a>:</h4>
<p>feels like an easy change to make and test</p>



<a name="163091295"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163091295" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163091295">(Apr 11 2019 at 11:33)</a>:</h4>
<p>But this does not generalise to multiplication, say.</p>



<a name="163091344"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163091344" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163091344">(Apr 11 2019 at 11:34)</a>:</h4>
<p>Is LLVM really able to figure out that it should just look at the overflow flag of the operation instead of doing the comparison on all the relevant architectures?</p>



<a name="163114512"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163114512" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163114512">(Apr 11 2019 at 16:17)</a>:</h4>
<p>yes, this is only for uadd and usub, everything else has more complicated expansions and it makes sense to use the overflow intrinsics for that.</p>



<a name="163114643"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163114643" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163114643">(Apr 11 2019 at 16:19)</a>:</h4>
<p>uadd.with.overflow and usub.with.overflow are formed during CGP in a target-independent way, though there are TLI hooks to opt out</p>



<a name="163114824"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163114824" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163114824">(Apr 11 2019 at 16:21)</a>:</h4>
<p>Though having checked just now, it looks like the usubo formation is disabled by default and only x86 opts in.</p>



<a name="163114936"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163114936" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163114936">(Apr 11 2019 at 16:22)</a>:</h4>
<p>what about i128/u128 on, say 32-bit targets?</p>



<a name="163115023"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163115023" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163115023">(Apr 11 2019 at 16:23)</a>:</h4>
<p>I recall changing expansion for uaddo i128 to be better in LLVM… I think.</p>



<a name="163115040"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163115040" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163115040">(Apr 11 2019 at 16:23)</a>:</h4>
<p>ah no that was umulo</p>



<a name="163115089"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163115089" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163115089">(Apr 11 2019 at 16:24)</a>:</h4>
<p>I guess it works then.</p>



<a name="163115109"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163115109" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163115109">(Apr 11 2019 at 16:24)</a>:</h4>
<p>It's only going to be done if uaddo/usubo are actually non-expand. If they aren't, it will be expanded back to add/sub + setcc anyway.</p>



<a name="163115113"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163115113" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163115113">(Apr 11 2019 at 16:24)</a>:</h4>
<p>if anybody is interested in making change to rust, I could tell where to look, it is a fairly easy change that can be done entirely in the library to test the waters.</p>



<a name="163115251"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163115251" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163115251">(Apr 11 2019 at 16:26)</a>:</h4>
<p><a href="https://github.com/rust-lang/rust/blob/9ebf47851a357faa4cd97f4b1dc7835f6376e639/src/libcore/num/mod.rs#L1331" target="_blank" title="https://github.com/rust-lang/rust/blob/9ebf47851a357faa4cd97f4b1dc7835f6376e639/src/libcore/num/mod.rs#L1331">https://github.com/rust-lang/rust/blob/9ebf47851a357faa4cd97f4b1dc7835f6376e639/src/libcore/num/mod.rs#L1331</a> and friends</p>



<a name="163115297"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163115297" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163115297">(Apr 11 2019 at 16:26)</a>:</h4>
<p>Might be hard to get actual perf data though</p>



<a name="163139599"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163139599" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> dlrobertson <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163139599">(Apr 11 2019 at 21:41)</a>:</h4>
<blockquote>
<p>With that, I think we have all the missing InstCombine bits for with.overflow intrinsics.</p>
</blockquote>
<p>Nice!</p>



<a name="163666742"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/add%20nsw%20%2B%20sadd.with.overflow/near/163666742" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/add.20nsw.20.2B.20sadd.2Ewith.2Eoverflow.html#163666742">(Apr 18 2019 at 16:27)</a>:</h4>
<p>For the record, <a href="https://reviews.llvm.org/D60650" target="_blank" title="https://reviews.llvm.org/D60650">https://reviews.llvm.org/D60650</a> and <a href="https://reviews.llvm.org/D60656" target="_blank" title="https://reviews.llvm.org/D60656">https://reviews.llvm.org/D60656</a> improve with.overflow handling in LVI/CVP, which is where LLVM performs non-local range based optimizations.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>